1. Field of the Invention
The present invention relates to the field of transactional memory utilization in parallel computing and more particularly to conflict arbitration in transactional memory management.
2. Description of the Related Art
Transactional memory techniques attempt to simplify parallel programming by allowing a group of load and store instructions to execute in an atomic way. Generally speaking, transactional memory is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. However, unlike the locking techniques used in most modern multithreaded applications, transactional memory can be viewed as optimistic in that a thread completes modifications to shared memory without regard for the activities of other threads, while recording every performed read and write and buffering the speculative changes to memory.
Transactions conflict when two or more transactions access the same block of memory, and at least one of those accesses is a write access. When utilizing transactional memory, instead of placing the onus on the reader or writer of a block of memory to ensure that the execution of a transaction does not conflict with other transactions in progress, the onus is placed on the transactional memory system to verify that other threads have not concurrently made conflicting references to the block of memory. Such a transactional memory system can be realized in software, hardware, or a combination of the two. The operation in which memory references are checked against other concurrent memory references is often referred to as validation. If validation is successful, at the conclusion of a transaction all memory changes are made permanent in an operation often referred to as a commit. Yet, a transaction can abort at any time, causing all of prior changes performed by the transaction to be rolled back or undone. If a transaction cannot be committed due to conflicting changes, the transaction can be aborted and re-executed from the beginning until the transaction succeeds.
It will be recognized by the skilled artisan, then, that the benefit of the optimistic approach of transactional memory is increased concurrency. Specifically, in the optimistic approach known in the art, no thread of execution need to wait to access a block of memory. Further, different threads of execution can safely and simultaneously modify disjoint parts of a data structure that would otherwise be protected under the same lock. Overall, despite the overhead incurred in retrying failed transactions, in many realistic programs conflicts arise rarely enough that transactional memory techniques may provide an immense performance gain over lock-based protocols on large numbers of processors.
Conflict arbitration is the mechanism for deciding which transactions will be blocked or aborted when a conflict occurs, and which transactions will be allowed to continue execution. Conflict arbitration is controlled by an underlying contention management policy. Simple conflict arbitration mechanisms have been proposed for transactional memory systems, such as aborting a transaction when the transaction attempts to access data conflicting with an access of the same data by another active transaction. More recent research, however, has indicated the importance of better contention management. Better contention management avoids “livelock” that becomes possible in simple contention management policies, and better contention management can substantially improve performance in the case of frequent conflicts. A sophisticated contention management policy can combine the temporary blocking of a transaction attempting a conflicting access while awaiting a successful commit by a competing transaction, with heuristics to maximize transaction throughput, and also with mechanisms to improve fairness or provide better guarantees of forward progress. Even still, while some contention management policies demonstrate good performance across a set of benchmarks or applications, no single policy has been found that is universally optimal.